1. Field of the Invention
The present invention relates to network technology. More particularly, the present invention relates to resource allocation in a network.
2. Description of the Related Art
Service providers may choose to make different levels of service available to customers, typically with corresponding differences in price. For example, some customers may need relatively higher data transfer rates than others and are willing to pay a premium for a higher quality of service (“QoS”) that can provide such transfer rates. Other customers may be content with a slower and less expensive service. Still other customers may wish to receive a higher QoS for certain services (e.g., voice) and a lower for QoS for other services (e.g., non-critical data). A service provider typically distinguishes between such customers based on configuration files assigned to different classes of customers.
Often the usage of network resources by a customer is metered or limited by measuring the amount bandwidth consumed by that customer's traffic as it is submitted to the service provider's network. The term “committed information rate” (“CIR”) is often used to denote the maximum amount of bandwidth able to be consumed by a particular customer as measured over some period of time. To allow for fluctuations in the flow of traffic submitted to the network, it is also possible to define an allowable “burstiness.” This is often called the “peak information rate” (“PIR”). IETF Request for Comments 2697, “A Single Rate Three Color Marker” and IETF Request for Comments 2698, “A Two Rate Three Color Marker” describe exemplary CIRs and PIRs and are hereby incorporated by reference for all purposes.
The bandwidth (i.e., number of bits/seconds) of the traffic submitted by the customer to the service provider is used as a proxy for the amount of network resources that traffic will consume as it traverses the service provider network. Network resources may include such items as buffering, CPU cycles, memory, CAM entries, etc.
A customer may have an aggregate CIR and individual “granular” CIRs and/or PIRs for various types of information (e.g., voice, video, data, etc.) For example, a particular customer may have an aggregate CIR of 10 Mb/s, including granular CIRs of 2 Mb/s for voice, 3 Mb/s for data and 5 Mb/s for video information.
All of these types of information will tend to be “bursty,” meaning that there will be times when no information is transmitted and other times when large amounts of information need to be transmitted. In order to regulate bursty traffic, network administrators need to ensure that network resources are allocated in a fair and predictable manner, i.e., one customer's burst of traffic should not limit the traffic flow, submitted by another customer, that conforms with the level of resources allocated for that customer.
Network resources, however, may be considered a “perishable” quantity in the sense that once an opportunity to transmit data has passed, it cannot be retrieved.
Service providers are, therefore, driven by two conflicting forces. The first is the need to ensure an equitable division of resources. The second is the desire to maximize the use of available network resources, which can be linked to potential revenue opportunities. The challenge lies in allowing some customers to burst the amount of traffic submitted while ensuring simultaneously that other customers are not “starved” for resources should they choose to send traffic.
A common method of regulating and shaping bursty traffic patterns is implemented by classifying data packets with a “token bucket.” As used herein, the terms “packet,” “frame” and the like will be used generically to mean atomic units of information and should not be interpreted as referring only to one particular protocol, layer, etc. FIG. 1 illustrates token bucket 180, which is used to determine whether a data packet is “conforming” or “non-conforming” with specified parameters. Packets classified as conforming may be, for example, transmitted to their intended destination. Packets classified as non-conforming may be dropped or given a reduced level of service, according to the particular implementation and service definition.
Tokens 185 may be considered authorizations for transmitting a predetermined unit of data; therefore, tokens are usually measured in bits or bytes. Tokens 185, which are represented as drops in FIG. 1, flow into token bucket 180 at a fixed rate R, which is measured in data units per time unit (e.g., bits or bytes per second). In this example, token bucket 180 has a capacity or volume of V 190 data units. Volume V is related to the maximum data burst that can be sent and still be conforming with respect to token bucket 180.
Typically, one or more token buckets are used to enforce each bandwidth profile. A particular traffic flow may then be subjected to a particular bandwidth profile. Thus, one or more token buckets are used to enforce a bandwidth profile for each traffic flow CIR is an attribute of the bandwidth profile and is related to the amount of traffic that a customer could send over a long period of time and have every packet be conforming. For example, one token bucket may be used in connection with a CIR for voice information and another token bucket may be used in connection with a CIR for data. Other token buckets may be associated with, for example, a PIR for each type of information.
Packets are classified according to whether they are conforming or non-conforming. In some preferred embodiments, packets are classified according to a color scheme such as that implemented in the above-referenced IETF Requests for Comment (red, yellow and green). However, any appropriate classification scheme may be used.
For example, suppose the next data packet 196 awaiting transmission in buffer 195 has a size of b data units, where V>b. If token bucket 180 is full, data packet 196 is a “conforming” packet. According to some implementations, data packet 196 would be marked “green” to indicate that it is a conforming packet. The same result would obtain, for example, at times when token bucket 180 contains tokens for at least b data units. Once it has been determined that a packet is conforming, b tokens 185 are removed from the token bucket 180.
However, if token bucket 180 contains tokens for fewer than b data units, data packet 196 is not conforming. According to some embodiments, non-conforming data packets 196 may be marked with another color, e.g., yellow or red.
Conforming and non-conforming data packets may be treated in various ways according to the particular implementation. For example, conforming data packet 196 may be sent immediately while a non-conforming packet may be discarded.
Typically, if a subscriber is not transmitting data, token bucket 180 reaches its capacity 190 in a relatively short time, for example, on the order of a second. After token bucket 180 reaches its capacity 190, additional new tokens, now termed excess tokens, are discarded. These discarded tokens represent unused network resources. It would be desirable to allocate more efficiently the total CIR of a customer. It would also be desirable, in some instances, to allocate flexibly the unused bandwidth of one customer to another customer or another service for the same customer.